package kgame5.kgu.ai.lianlian {
/**
 * @author kangkai
 * 连连看的寻径算法，比PathFinder要快很多的，比较适合再简单地图下使用。
 * 其实一般游戏里有这个就很可以了！！最大的优点是这个的速度非常快啊
 * 这个还包括生成随机地图和检测游戏是否完毕
 */
import kgame5.kmath.MathDG;
import kgame5.kutil.*;

public class LianLian{
	
	//判断能否消掉,返回的是一个2维数组,[col,row],表示路径,null就是说没找到路径
	//startCellInfo是一个cell的信息，就是{col,row,cellType}
	
	// 寻路算法
	// 可以不使用递归，两张牌连通性有三种可能：直接连通，转折一次或者转折两次。
	// 直接连通比较简单，只需要判断两张牌之间连线上是否存在阻碍点即可
	// 转折一次，取到转折点——即此两点形成的矩形的另外两个顶点，然后判断两点与转折点之间是否联通
	// 转折两次，将起始点向四个方向进行扩展，生成四个方向上的空格序列，然后将每个空格作为起始点与终点寻找转折一次的通路
	public function CanKill(
		start:Object, end:Object,
		a2MapData:Array//地图的2维数组
		):Array {
		
		if(start.cellType!=end.cellType){
			return null;
		}
		
		var a2Route:Array=new Array();
		
		// 两点直接连通
		if (link_straight(start, end,a2MapData)) {
			a2Route.push([start.col,start.row]);
			a2Route.push([end.col,end.row]);
			return a2Route;
		}
		// 两点转折一次连通
		var corner:Object = link_one_corner(start, end,a2MapData);
		if (corner != null) {
			a2Route.push([start.col,start.row]);
			a2Route.push([corner.col,corner.row]);
			a2Route.push([end.col,end.row]);
			return a2Route;
		}
		// 需要转折两次，扩展起始点
		var list:Array = expend_point(start, end,a2MapData);
		for (var i:int = 0; i < list.length; i ++) {
			var tc:Object = link_one_corner(list[i], end,a2MapData);
			if (tc != null) {
				a2Route.push([start.col,start.row]);
				a2Route.push([list[i].col,list[i].row]);
				a2Route.push([tc.col,tc.row]);
				a2Route.push([end.col,end.row]);
				return a2Route;
			}
		}
		// 找不到路径
		return null;
	}
	
	// 判断两点之间是否直接连通
	private function link_straight(
		start:Object, end:Object,
		a2MapData:Array//地图的2维数组
		):Boolean {
		if (start.col == end.col) {		// 两点在同一列
			var startRow:Number = Math.min(start.row, end.row) + 1;
			var endRow = Math.max(start.row, end.row);
			var col = start.col;
			for (var r=startRow; r < endRow; r++) {
				if (a2MapData[r][col] != 0) {
					return false;	// 有阻碍
				}
			}
			return true;
		} else if (start.row == end.row) {	// 两点在同一行
			var startCol = Math.min(start.col, end.col) + 1;
			var endCol = Math.max(start.col, end.col);
			var row = start.row;
			for (var c=startCol; c <endCol; c ++) {
				if (a2MapData[row][c] != 0) {
					return false;	// 有阻碍
				}
			}
			return true;
		} else {	// 两点不在同一直线上
			return false;
		}
	}
	
	// 判断两点经过一次转折是否连通
	private function link_one_corner(
		start:Object, end:Object,
		a2MapData:Array//地图的2维数组
		):Object {
		var sc:int = start.col;
		var ec:int = end.col;
		var sr:int = start.row;
		var er:int = end.row;
		
		var cp:Object;
		
		if (a2MapData[sr][ec] == 0) {	// 转折点1
			cp ={col:ec,row:sr,cellType:0};// new CellInfo(ec,sr,0);
			//cp.col = ec;
			//cp.row = sr;
			//cp.cellType=0;//a2MapData[sr][ec]
			
			if (link_straight(start, cp,a2MapData) && link_straight(end, cp,a2MapData)){
				 return cp;
			}
		}
		if (a2MapData[er][sc] == 0) {	// 转折点1
			cp = {col:sc,row:er,cellType:0};//new CellInfo(sc,er,0);
			//cp.col = sc;
			//cp.row = er;
			//cp.cellType=0;//a2MapData[sr][ec]
			
			if (link_straight(start, cp,a2MapData) && link_straight(end, cp,a2MapData)){
				 return cp;
			}
		}
		
		return null;
	}
	
	// 从生成起始点向四方向扩展可到达空点，不包含直接转折点
	private function expend_point(
		start:Object, end:Object,
		a2MapData:Array//地图的2维数组
		):Array {
		var list:Array = new Array();
		
		var sc:Number = start.col;
		var ec:Number = end.col;
		var sr:Number = start.row;
		var er:Number = end.row;
		
		var CC:Number = a2MapData[0].length;
		var RC:Number = a2MapData.length;
		
		var r:int ,c:int;
		// 向上扩展起始点
		
		for(r=sr-1;r>=0;r--){
			if (a2MapData[r][sc] == 0) {		// 空格
				if (r !=er) {		// 一次转折点不放入队列
					//var tmp = new Object();
					//tmp.col = sc;
					//tmp.row = r;
					//tmp.cellType = 0;
					
					
					
					//list.push(tmp);
					list.push({col:sc,row:r,cellType:0});
				}
			} else {		// 遇到阻碍退出
				break;
			}
		}
		// 向下扩展起始点
		
		for(r=sr+1;r<RC;r++){
			if (a2MapData[r][sc] == 0) {		// 空格
				if (r != er) {		// 一次转折点不放入队列
				/*
					var tmp = new Object();
					tmp.col = sc;
					tmp.row = r;
					tmp.cellType = 0;
					
					list.push(tmp);
					//*/
					list.push({col:sc,row:r,cellType:0});//new CellInfo(sc,r,0));
				}
			} else {		// 遇到阻碍退出
				break;
			}
			
		}
		// 向左扩展起始点
		
		for(c=sc-1;c>=0;c--){
			if (a2MapData[sr][c] == 0) {		// 空格
				if (c != ec) {		// 一次转折点不放入队列
					//var tmp = new Object();
					//tmp.col = c;
					//tmp.row = sr;
					//tmp.cellType = 0;
				
					//list.push(tmp);
					list.push({col:c,row:sr,cellType:0});
				}
			} else {		// 遇到阻碍退出
				break;
			}
		}
		// 向右扩展起始点
		
		for(c=sc+1;c<CC;c++){
			if (a2MapData[sr][c] == 0) {		// 空格
				if (c != ec) {		// 一次转折点不放入队列
					var tmp = new Object();
					//tmp.col = c;
					//tmp.row = sr;
					//tmp.cellType = 0;
					
					//list.push(tmp);
					list.push({col:c,row:sr,cellType:0});//new CellInfo(c,sr,0));
				}
			} else {		// 遇到阻碍退出
				break;
			}
			
		}
		//trace("表");
		//t(list);
		return list;
	}
	/*
	private function t(list){
		trace("!!");
		for(var i=0;i<list.length;i++){
			trace(list[i].col+" "+list[i].row);
		}
	}
	//*/
	////////////////////
	
	///////////
	// 查询局面 0是没有结束,1是消干净了，-1是没消干净
	//[0]结果，0是消干净了，1是没消干净但是还有，-1是没消干净并且死了
	//Object结果
	//result:
	//a:
	//b:
	public function CheckGame(a2MapData:Array):Object {
		var list:Array=new Array();//cellInfo的list, list[i]={col,row,cellType}
		//1,把剩下的cell都放到一个队列里去
		for(var r:int=0;r<a2MapData.length;r++){
			for(var c:int=0;c<a2MapData[0].length;c++){
				var cellType:Number=a2MapData[r][c];
				if(cellType!=0){
					list.push({col:c,row:r,cellType:cellType});
				}
			}
		}
		//如果list=0,就是消干净了
		if(list.length==0){
			return {result:0};//消干净了
		}
		//2,找到一个可以消除的就可以了
		var len:Number=list.length;
		for(var i:int=0;i<len-1;i++){
			var a:Object=(list[i]);
			for(var j:int=i+1;j<len;j++){
				var b:Object=(list[j]);
				var kkk:Array=this.CanKill(a,b,a2MapData);
				if(kkk==null){//没有路的结果
				}else{//有路就可以
					T.p("可以消:");
					T.p(a.col+" "+a.row+" ");
					T.p(b.col+" "+b.row+" ");
					return {result:1,cellInfoA:a,cellInfoB:b};
				}
			}
		}
		return {result:-1};//有但是已经死了
	}
	//生成一个2维数组,a2Template是一个模板,1表示在这个地方可以放，0表示不可以放
	public function GenMap(CC:Number,RC:Number,a2Template:Array):Array{
		var a2MapData:Array=Util.NewArray2_Int(RC,CC);
		
		var freeCellList:Array=new Array();
		for(var r:int=0;r<RC;r++){
			for(var c:int=0;c<CC;c++){
				if(a2Template!=null&&a2Template[r][c]!=0){//如果使用摸板可以在这里放东西
					freeCellList.push({col:c,row:r,cellType:-1});
				}else{
					freeCellList.push({col:c,row:r,cellType:-1});
				}
			}
		}
		T.p("!!"+freeCellList[0].col);
		
		for(var i:int=0;i<CC*RC/2;i++){
			var cellType:Number=MathDG.random(1,10);
			
			var idxA:Number=MathDG.random(0,freeCellList.length-1);
			var cellInfoA:Object=freeCellList.splice(idxA,1)[0];
			
			//cellInfoA.trace();
			
			a2MapData[cellInfoA.row][cellInfoA.col]=cellType;

			var idxB:Number=MathDG.random(0,freeCellList.length-1);
			var cellInfoB:Object=freeCellList.splice(idxB,1)[0];
			
			//cellInfoB.trace();
			
			a2MapData[cellInfoB.row][cellInfoB.col]=cellType;
		}
		
		//T.p("生成的数组为:");
		//T.lc_sender(a2MapData);
		
		return a2MapData;
	}
}//end of class
}